\section{Extension to $\rho$-Dynamic Networks}

%\subsection{Maintaining approximated densest subgraphs}
%
%Maintaining some subgraphs so that we can answer the query "what is the density of the densest subgraph of size at least k?" quickly.

%\subsection{$\rho$-dynamic network}


From Danupon's email ... (See the commented text)
%
%As I've mentioned in the last two meetings, I now believe that we should try to settle the "right" model before we start writing the paper. Ideally, I think we should stay as close to Lynch et al.'s dynamic network model as possible but we should add some assumptions such that, any other assumption we can think of is a special case of this assumption.
%
%Here's my attempt on this. I would like to propose the assumption of T-interval \alpha-locally \rho-dynamic network. It sounds quite natural to me and, although it doesn't fully cover all other possible assumptions we can come up with, it seems to capture many of them (more on this later).
%
%To motivate this notion, let me first define the notion of T-interval \rho-dynamic network, for any integer T and 0\leq \rho\leq 1. This notion says that there are at most \rho fraction of edges added and deleted during any time interval of length T, i.e., |E(G_t)\E(G_{t+T}|+|E(G_{t+T})\E(G_t)| \leq \rho |E(G_t)|. Note that this capture how dynamic the network is in the sense that static networks are T-interval 0-dynamic (for any T) and fully dynamic networks are T-interval 1-dynamic.
%
%(Note that I believe that we can define \rho-dynamic instead of T-interval \rho-dynamic. This sounds even more natural. I have to think a bit more on this.)
%
%The problem with the above notion is that is doesn't say anything about local property of the network. If we think of a huge network (e.g., internet over the world), this notion really doesn't say much. Moreover, many dynamic network should maintain it's property even on it's (large enough) subgraph. So, it's natural to extend this notion to T-interval locally \rho-dynamic network. This says that any subgraph must be T-interval \rho-dynamic.
%
%The problem is now that the second notion is too strong as it requires even a subgraph of two nodes to be T-interval \rho-dynamic. To strike the balance, we consider the notion of T-interval \alpha-locally \rho-dynamic, for any 0\leq \alpha\leq 1. This notion says that every subgraph of size at least (\alpha n) should be T-interval \rho-dynamic (size can be interpret as both number of edges and nodes; this depends on our preference). This seems to capture the notion that large subgraphs still have the same property as the whole graph. Also note that the first notion is equivalent to \alpha=1 while the second notion is equivalent to \alpha=0. So, this notion captures all range of the locality and dynamicity of the network.
%
%Observe that we can solve the at least (\alpha n) problem when the network is T-interval \alpha-locally \rho-dynamic, for any constant \rho. Moreover, I believe that we don't need to assume that the graph is connected (thus it covers the node deletion/addition model; this is not the case even in the previous papers by Lynch et al.). (Note that nodes that are not connected might not know the answer in the end in this model and we may have to assume that nodes know the total number of nodes in the beginning.) Moreover, our previous model of edge deletion/addition (1 per time interval) implies that the network is roughly 1-interval 2/n-locally (1/2)-dynamic.
%
%Note that one problem with this notion is that it doesn't capture the assumption that the densest subgraph has density at least D\log n. But I guess we can somehow extend it.
%
%I guess the first thing we have to discuss is whether you think we can use something like this or prefer to stay on the previous model.
%
%Some minor questions that we can explore (if we agree to use some notion like this).
%- Does this imply T-interval connectivity?
%- Can we say something about D_max and dynamic diameter in this case? Note again that I don't think that this is crucial.
%- Can we extend our algorithm to detect how dynamic the network is, i.e., can we detect if there is a (large) subgraph there is not T-interval \rho-dynamic?
%
%
%There also some papers that we can later explore and can relate our result to.
%- Analysis of Shortest-Path Routing Algorithms in a Dynamic Network Environment (ACM SIGCOMM Computer Communication). This paper talks about the notion of  static, quasi-static and dynamic. Our notion is somewhere between quasi-static and dynamic. "... the quasi-static category, in which the link distances remain constant for short period of time (eg. 10 seconds in SPF) but can be updated when signi?cant changes occur."
%
%- http://www.ee.scu.edu/eefac/siljak/papers/Dynamic%20Graphs_Conf.pdf. This paper talks about stability of dynamic graphs in many senses and have many pointers. We might be able to get some idea from the papers in this area.
%
%- It seems that there are many papers that talk about "stability of dynamic graphs" in other areas as well (just search "stability dynamic graph" on google). I believe that many of models will have the property that I defined above.
%
%- http://en.wikipedia.org/wiki/Network_dynamics 